#pragma once

///结点结构
template <typename E>
struct LNode
{
    E data;      //数据域
    LNode *next; //指针域
};

///链表类型
// typedef LNode *LinkList；// for C
template <typename E>
using LinkList = LNode<E> *; // for c++11

///初始化链表为空表 InitList(&L)
template <typename E>
void InitList(LinkList<E> &L)
{
    L = new LNode<E>;
    L->next = nullptr;
}

///链表插入 ListTnsert(&L,i,e)
template <typename E>
void ListInsert(LinkList<E> &L, int i, E e)
{
    //查找第 i-1 个结点 p
    auto p = L;
    int j = 0;
    while(p && j < i - 1)
    {
        p = p->next;
        ++j;
    }

    //若 p 存在，在其后插入 e
    if (p && j == i - 1)
    {
        //新建结点 s, 保存 e
        auto s = new LNode<E>;
        s->data = e;
        //在p之后插入s
        s->next = p->next;
        p->next = s;
    }
    else
    {
        throw "Invalid i";
    }
}

/// 链表删除 LIstDelete(&L,i,&e)
template <typename E>
void ListDelete(LinkList<E> &L, int i, E &e)
{
    //查找第i-1个结点 p
    auto p = L;
    int j = 0;
    while (p && j < i - 1)
    {
        p = p->next;
        ++j;
    }

    //若第1 个 结点存在，则删除
    if (p && j == i - 1 && p->next)
    {
        // 取出数据元素，用e 返回
        auto q = p->next; // 指向第 1 个结点
        e = q->data;
        //删除第一个结点 q
        p->next = q->next;
        delete q;
    }
    else
    {
        throw "Invalid i";
    }
}